package com.example.hot100;


/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *  单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  示例 1：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word ="ABCCED"
 * 输出：true
 *
 *  示例 2：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word ="SEE"
 * 输出：true
 *
 *  示例 3：
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
 * "ABCB"
 * 输出：false
 */
public class Leetcode79_Exist {
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
        String word ="ABCCED";

        System.out.println(new Solution().exist(board, word));
    }

    static class Solution {
        private int[][] directs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        public boolean exist1(char[][] board, String word) {
            int rows = board.length, columns = board[0].length;
            if (rows * columns < word.length()) return false;
            char[] chars = word.toCharArray();
            boolean[][] visited = new boolean[rows][columns]; // 同一字符不能重复使用
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    if (dfs(board, chars,visited, i, j, 0)) return true;
                }
            }
            return false;
        }

        private boolean dfs(char[][] board, char[] word, boolean[][] visited, int x, int y, int wordIndex) {
            int rows = board.length, columns = board[0].length;

            if (board[x][y] == word[wordIndex]) {
                if (wordIndex == word.length - 1) {
                    return true;
                }

                visited[x][y] = true;
                for (int k = 0; k < directs.length; k++) {
                    int newX = x + directs[k][0], newY = y + directs[k][1];
                    if (newX >= 0 && newX < rows && newY >= 0 && newY < columns) {
                        if (!visited[newX][newY]
                                && dfs(board, word, visited, newX, newY, wordIndex + 1)) return true;
                    }
                }
                visited[x][y] = false; // 恢复本次遍历的地方
                return false;
            } else {
                return false;
            }

        }

        public boolean exist(char[][] board, String word) {
            return exist1(board, word);
        }
    }
}
